InBiauetal.(2008),theyemploy the randomized sketches method to project the data in Hilbert space so as to approximate kernel k-means. However, the data in Hilbert space are implicit and infinite-dimensional, and its sketch matrixisdenseandunstructured.

InBiauetal.(2008),theyemploy the randomized sketches method to project the data in Hilbert space so as to approximate kernel k-means. However, the data in Hilbert space are implicit and infinite-dimensional, and its sketch matrixisdenseandunstructured.

Kernel $k$-means is arguably one of the most common approaches to clustering. In this paper, we investigate the efficiency of kernel $k$-means combined with randomized sketches in terms of both statistical analysis and computational requirements. More precisely, we propose a unified randomized sketches framework to kernel $k$-means and investigate its excess risk bounds, obtaining the state-of-the-art risk bound with only a fraction of computations. Indeed, we prove that it suffices to choose the sketch dimension $\Omega(\sqrt{n})$ to obtain the same accuracy of exact kernel $k$-means with greatly reducing the computational costs, for sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystr\{o}m kernel $k$-means, where $n$ is the number of samples. To the best of our knowledge, this is the first result of this kind for unsupervised learning.

Post-rebuttal update: The author's rebuttal addresses my (minor) concerns well, and my overall score remains the same. The approach is similar to earlier work such as: - M. Pilanci and M. J. Wainwright. The main innovations here are to extend this sketching technique to a wider class of convex objectives and to introduce a data-adaptive sketching technique that greatly improves the error bounds on the solution relative to a data-oblivious sketch. The proposed technique can also be performed iteratively to improve the accuracy of the solution without having to change the sketch matrix, so the sketch on the data only has to be performed once. Overall, I thought this was a high-quality paper.

Kernel k -means is arguably one of the most common approaches to clustering. In this paper, we investigate the efficiency of kernel k -means combined with randomized sketches in terms of both statistical analysis and computational requirements. More precisely, we propose a unified randomized sketches framework to kernel k -means and investigate its excess risk bounds, obtaining the state-of-the-art risk bound with only a fraction of computations. Indeed, we prove that it suffices to choose the sketch dimension \Omega(\sqrt{n}) to obtain the same accuracy of exact kernel k -means with greatly reducing the computational costs, for sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystr\"{o}m kernel k -means, where n is the number of samples. To the best of our knowledge, this is the first result of this kind for unsupervised learning.

This paper considers the partially functional linear model (PFLM) where all predictive features consist of a functional covariate and a high dimensional scalar vector. Over an infinite dimensional reproducing kernel Hilbert space, the proposed estimation for PFLM is a least square approach with two mixed regularizations of a function-norm and an $\ell_1$-norm. Our main task in this paper is to establish the minimax rates for PFLM under high dimensional setting, and the optimal minimax rates of estimation is established by using various techniques in empirical process theory for analyzing kernel classes. In addition, we propose an efficient numerical algorithm based on randomized sketches of the kernel matrix. Several numerical experiments are implemented to support our method and optimization strategy.